/*
 * PageRank.cpp
 *
 *  Created on: Jun 14, 2011
 *      Author: lucmir
 */

#include "PageRank.h"

PageRank::PageRank() {

}

PageRank::~PageRank() {
}


/**
 * Function for calculating pageRank for documents
 */
void PageRank::calculatePageRank(std::ifstream &inFile, std::ofstream &outFile) {
	EdgeListType forward;
	unsigned int maxPageNum, removedLinks;

	// Default parameters
	int maxIters = DEFAULT_MAX_ITERATIONS;
	double epsilon = DEFAULT_EPSILON;
	double EVecNorm = DEFAULT_E_NORM;

	// Read edge list from file
	forward.reserve(DEFAULT_LINKS);
	readEdgeList(inFile, forward, maxPageNum);

	vector<double> E(maxPageNum + 1, 0);
	fill(E.begin(), E.end(), (EVecNorm / (maxPageNum + 1)));

	// Accumulate out degrees
	vector<int> outDeg(maxPageNum + 1, 0);
	for_each(forward.begin(), forward.end(), DegreeUpdater(outDeg));

	// Remove dangling links
	EdgeListType::iterator forwardEnd = forward.end();
	EdgeListType::iterator newForwardEnd;
	stack<EdgeListType::iterator> partitions;
	vector<int> outDegTmp = outDeg;
	partitions.push(forwardEnd);
	do {
		partitions.push(forwardEnd);
		newForwardEnd = partition(forward.begin(), forwardEnd, Undangler(
				outDegTmp));
		removedLinks = (forwardEnd - newForwardEnd);
		forwardEnd = newForwardEnd;
	} while (removedLinks > 0);

	// Map with the back links of each node
	AdjMapType backLinks;
	for (EdgeListType::const_iterator it = forward.begin(); it != forwardEnd; ++it) {
		backLinks.insert(make_pair(it->second, it->first));
	}

	// Compute the page ranks
	int N = E.size();
	vector<double> R[2], tmp(N, 0);
	int p = 1, n = 0;
	R[0] = E;
	R[1].resize(N);

	int iteration = 0;
	double delta;
	do {
		swap(p, n);
		fill(R[n].begin(), R[n].end(), 0);

		//TRACE << "On iteration " << iteration << ":" << endl;
		//TRACE << " ||Rp|| = " << calculateL1Norm(R[p]) << endl;

		for (AdjMapType::const_iterator it = backLinks.begin(); it
				!= backLinks.end(); ++it) {
			int u = it->first;
			int v = it->second;
			R[n][u] += R[p][v] / outDeg[v];
		}
		//TRACE << " ||Rn|| = " << L1_norm(R[n]) << endl;

		double d = calculateL1Norm(R[p]) - calculateL1Norm(R[n]);
		//TRACE << " d = " << d << endl;

		// Calculate R[n] = R[n] + d*E;
		for (int i = 0; i < N; ++i) {
			R[n][i] = R[n][i] + d * E[i];
		}

		// Calculate delta = ||R[n] - R[p]||_1
		for (int i = 0; i < N; ++i) {
			tmp[i] = R[n][i] - R[p][i];
		}
		delta = calculateL1Norm(tmp);
		//TRACE << " delta = " << delta << endl;

		++iteration;
	} while (iteration < maxIters && delta > epsilon);

	// Deal with dangling links
	for (EdgeListType::iterator it = forwardEnd; it != forward.end(); ++it) {
		R[n][it->second] = 0;
	}
	while (partitions.size() > 1) {
		EdgeListType::iterator it = partitions.top();
		partitions.pop();
		EdgeListType::iterator part_end = partitions.top();
		for (; it != part_end; ++it) {
			R[n][it->second] += R[n][it->first] / outDeg[it->first];
		}
	}

	// Renormalizing
	double norm_const = calculateL1Norm(R[n]);
	for (int i = 0; i < N; ++i) {
		R[n][i] /= norm_const;
	}

	// Output sorted descending by rank.
	vector<int> pi(N);
	for (int i = 0; i < N; ++i) {
		pi[i] = i;
	}
	sort(pi.begin(), pi.end(), PermComparator<double> (R[n]));
	for (int i = N - 1; i >= 0; --i) {
		outFile << pi[i] << " " << R[n][pi[i]] << endl;
	}
}


/**
 * Function for calculating L1 norm
 */
double PageRank::calculateL1Norm(const vector<double>& v) {
	double norm = 0.0;

	for (vector<double>::const_iterator it = v.begin(); it != v.end(); ++it) {
		norm += fabs(*it);
	}

	return norm;
}

/*
 * Read edge list.
 */
void PageRank::readEdgeList(istream& input, EdgeListType &edges, unsigned int &maxPageNumber) {
	unsigned int pageNum, linkCount, link;
	maxPageNumber = 0;

	while (input.good()) {
		input >> pageNum >> linkCount;
		if (!input.good()) {
			break;
		}
		for (unsigned int i=0; i<linkCount; ++i) {
			input >> link;
			if (!input.good()) {
				exit(EXIT_FAILURE);
			}
			if (pageNum != link) {
				edges.push_back(make_pair(pageNum, link));
			}
		}
		if (pageNum > maxPageNumber) {
			maxPageNumber = pageNum;
		}
	}
}
